Danh sách Python ở cấp độ thấp không phải là danh sách liên kết lỏng lẻo, mà là một cấu trúc được tổ chức cao độ ArrayList. Điều cốt lõi là: nó chiếm một vùng địa chỉ liên tục trong bộ nhớ. Tại đây không lưu trữ chính đối tượng, mà là các tham chiếu đến đối tượng tham chiếu(ở mức độ ngôn ngữ C thì chính là con trỏ). Thiết kế này cho phép quản lý đồng nhất các loại dữ liệu khác nhau, dù là bộ ba màu (RGB) hay khóa mã hóa phức tạp (Key), đều chỉ cần chiếm một vị trí có kích thước cố định của con trỏ.

Toán học truy cập và cân bằng hiệu suất

• $O(1)$ truy cập ngẫu nhiên: Thông qua công thức $\text{địa chỉ phần tử} = \text{địa chỉ bắt đầu} + \text{chỉ số} \times \text{kích thước}$, CPU có thể xác định ngay lập tức.
• Phân tích trung bình (Phân tích trung bình): Sử dụng chiến lược phân bổ quá mức, mặc dù việc chèn một lần có thể là $O(n)$, nhưng $\text{tổng chi phí} = n + \sum_{j=0}^{\lg n} 2^j = 3n$, đảm bảo hiệu suất thêm vào trung bình là $O(1)$.
• Hạn chế chèn: Như Hình 8-2 minh họa, tại bất kỳ vị trí nào `insert`, tất cả các con trỏ phía sau đều phải di chuyển, độ phức tạp là $O(n)$.